package Graph.Medium;

import java.util.Deque;
import java.util.LinkedList;

public class LC0200 {
    int M, N;
    boolean[][] visited;

    public int numIslands(char[][] grid) {
        M = grid.length;
        N = grid[0].length;
        visited = new boolean[M][N];
        int nIslands = 0;

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (grid[i][j] == '1' && !visited[i][j]) {
                    nIslands++;
                    visited[i][j] = true;
                    bfs(i, j, grid);
                }
            }
        }

        return nIslands;
    }

    private void bfs(int i, int j, char[][] grid) {
        Deque<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            int[][] deltas = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
            for (int[] delta : deltas) {
                int x = pos[0] + delta[0];
                int y = pos[1] + delta[1];
                if (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == '1' && !visited[x][y]) {
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y});
                }
            }
        }
    }

    private void dfs(int i, int j, char[][] grid) {
        visited[i][j] = true;
        int[][] deltas = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int[] delta : deltas) {
            int x = i + delta[0];
            int y = j + delta[1];
            if (x >= 0 && x < M && y >= 0 && y < N && grid[x][y] == '1' && !visited[x][y]) {
                dfs(x, y, grid);
            }
        }
    }

    public static void main(String[] args) {
        int[][] gridInt = new int[][]{
                {1, 1, 1, 1, 0},
                {1, 1, 0, 1, 0},
                {1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0}};
        char[][] grid = convert(gridInt);
        LC0200 solver = new LC0200();
        System.out.println(solver.numIslands(grid));
    }

    private static char[][] convert(int[][] gridInt) {
        char[][] ret = new char[gridInt.length][gridInt[0].length];

        for (int i = 0; i < gridInt.length; i++) {
            for (int j = 0; j < gridInt[0].length; j++) {
                ret[i][j] = (char) ('0' + (char) gridInt[i][j]);
            }
        }

        return ret;
    }
}
